//
// Created by DaiZhe on 2018/5/22.
//
#include<iostream>

using namespace std;

// 通用元素类型声明
typedef int ElemType;

// ============= 二叉树的定义和相关操作 =============
struct BTreeNode {
    ElemType data;      //值域
    BTreeNode *left;    //指向左孩子结点的指针域
    BTreeNode *right;   //指向右孩子结点的指针域
};

//1. 初始化二叉树
void InitBTree(BTreeNode *&BT)
//初始化二叉树，即把树根指针置空
{
    BT = NULL;
}

//4. 求二叉树深度
int DepthBTree(BTreeNode *BT) {      //求由BT指针指向的一棵二叉树的深度
    if (BT == NULL)
        return 0;  //对于空树，返回0并结束递归
    else {
        int dep1 = DepthBTree(BT->left);      //计算左子树的深度
        int dep2 = DepthBTree(BT->right);     //计算右子树的深度
        if (dep1 > dep2)                       //返回树的深度
            return dep1 + 1;
        else
            return dep2 + 1;
    }
}

//6. 输出二叉树
void PrintBTree(BTreeNode *BT) {            //输出二叉树的广义表表示
    if (BT != NULL) {                       //树为空时结束递归，否则执行如下操作
        cout << BT->data;                   //输出根结点的值
        if (BT->left != NULL || BT->right != NULL) {
            cout << '(';                    //输出左括号
            PrintBTree(BT->left);           //输出左子树
            if (BT->right != NULL)
                cout << ',';                //若右子树不为空则首先输出逗号分隔符
            PrintBTree(BT->right);          //输出右子树
            cout << ')';                    //输出右括号
        }
    }
}

//7．清除一棵二叉树，使之变为一棵空树
void ClearBTree(BTreeNode *&BT) {
    if (BT != NULL) {
        ClearBTree(BT->left);           //删除左子树
        ClearBTree(BT->right);          //删除右子树
        delete BT;                      //释放根结点
        BT = NULL;                      //置根指针为空
    }
}

//9.中序遍历算法
void InOrder(BTreeNode *BT) {
    if (BT != NULL) {
        InOrder(BT->left);          //中序遍历左子树
        cout << BT->data << ' ';    //访问根结点
        InOrder(BT->right);         //中序遍历右子树
    }
}

// ============= 二叉搜索树相关操作 =============
//1. 查找算法-递归
bool Find(BTreeNode *BST, ElemType &item) {
    if (BST == NULL) return false;      //查找失败返回假
    else {
        if (item == BST->data) {        //若查找成功则带回元素值并返回真
            item = BST->data;
            return true;
        } else if (item < BST->data)    //向左子树继续查找
            return Find(BST->left, item);
        else                            //向右子树继续查找
            return Find(BST->right, item);
    }
}

//1'.查找算法-非递归
bool Find1(BTreeNode *BST, ElemType &item) {
    while (BST != NULL) {
        if (item == BST->data) {
            item = BST->data;
            return true;
        } else if (item < BST->data) {
            BST = BST->left;
        } else {
            BST = BST->right;
        }
    }
    return false;
}

//2. 更新算法-非递归
bool Update1(BTreeNode *BST, const ElemType &item) {
    while (BST != NULL) {               //循环查找待更新的结点
        if (item == BST->data) {        //进行更新并返回真
            BST->data = item;
            return true;
        } else if (item < BST->data) {   //向左子树查找
            BST = BST->left;
        } else {
            BST = BST->right;           //向右子树查找
        }
    }
    return false;                       //没有待更新的结点，返回假
}

//3. 插入算法-递归
void Insert(BTreeNode *&BST, const ElemType &item) {
    if (BST == NULL) {              //把值为item的新结点链接到已找到的插入位置
        BTreeNode *p = new BTreeNode;
        p->data = item;
        p->left = p->right = NULL;
        BST = p;
    } else if (item < BST->data) {
        Insert(BST->left, item);    //向左子树中插入元素
    } else {
        Insert(BST->right, item);   //向右子树中插入元素
    }
}

//3'.插入算法-非递归
void Insert1(BTreeNode *&BST, const ElemType &item) {
    //为插入新元素寻找插入位置，定义指针t并指向当前待比较的结点，初始
    //指向树根结点，定义指针parent指向t结点的双亲结点，初始为NULL
    BTreeNode *t = BST, *parent = NULL;
    while (t != NULL) {
        parent = t;
        if (item < t->data) t = t->left;
        else t = t->right;
    }
    //建立值为item，左、右指针域为空的新结点
    BTreeNode *p = new BTreeNode;
    p->data = item;
    p->left = p->right = NULL;
    //将新结点插入到二叉搜索树BST中
    if (parent == NULL) {
        BST = p;
    } else if (item < parent->data) {
        parent->left = p;
    } else {
        parent->right = p;
    }
}

//4. 建立二叉搜索树
void CreateBSTree(BTreeNode *&BST, ElemType a[], int n)
//利用数组中的n个元素建立二叉搜索树的算法
{
    BST = NULL;   //从空树开始建立
    for (int i = 0; i < n; i++)
        Insert(BST, a[i]);
}

//5. 删除算法
bool Delete(BTreeNode *&BST, const ElemType &item) {
    if (BST == NULL) return false;
    if (item < BST->data) return Delete(BST->left, item);
    if (item > BST->data) return Delete(BST->right, item);
    BTreeNode *temp = BST;
    if (BST->left == NULL) {
        BST = BST->right;
        delete temp;
        return true;
    } else if (BST->right == NULL) {
        BST = BST->left;
        delete temp;
        return true;
    } else {
        if (BST->left->right == NULL) {
            BST->data = BST->left->data;
            return Delete(BST->left, BST->left->data);
        } else {
            BTreeNode *p1 = BST, *p2 = BST->left;
            while (p2->right != NULL) {
                p1 = p2;
                p2 = p2->right;
            }
            BST->data = p2->data;
            return Delete(p1->right, p2->data);
        }
    }
}

int main() {
    ElemType x;
    BTreeNode *bst;
    InitBTree(bst);
    ElemType a[10] = {30, 50, 20, 40, 25, 70, 54, 23, 80, 92};
    CreateBSTree(bst, a, 10);
    PrintBTree(bst);
    cout << endl;

    cout << "深度：" << DepthBTree(bst) << endl;
    cout << "中序：";
    InOrder(bst);
    cout << endl;
    //x=70;
    cout << "输入一个待查找的整数值：";
    cin >> x;
    if (Find1(bst, x)) {
        cout << "查找成功" << x << "成功" << endl;
    } else {
        cout << "查找元素" << x << "失败" << endl;
    }

    cout << "输入一个待插入的整数值：";
    cin >> x;
    Insert1(bst, x);

    cout << "输入一个待删除的整数值：";
    cin >> x;
    if (Delete(bst, x)) {
        cout << "删除成功" << x << "成功" << endl;
    } else {
        cout << "删除元素" << x << "失败" << endl;
    }

    PrintBTree(bst);
    cout << endl;
    cout << "中序：";
    InOrder(bst);
    cout << endl;

    ClearBTree(bst);
}